The invention relates to the normalization of vectors (e.g., those used to implement shading) associated with display pixels of computer generated images.
In computer graphics, curved surfaces of three-dimensional objects are typically approximated by a plurality of flat surfaces, preferred to as polygons (typically triangles), that are bounded by straight edges that also bound adjacent polygons. The two-dimensional image that is displayed on a cathode ray tube (CRT) or printed is often broken up into a two-dimensional array of pixels, which are the smallest addressable components of an image. A plurality of pixels are used to display each triangle that is associated with a visible surface of the object being imaged.
To produce a realistic image, the intensities (i.e., brightnesses) of the pixels associated with each triangle are varied (i.e., shaded) in accordance with a shading model that takes into account the light sources, surface characteristics, and the positions and orientations of the surfaces and sources. The shading model employs an illumination equation (e.g., equation (1) herein, discussed in detail below) that includes vectors that are normal to the object surface (referred to as "normals") and further vectors; to describe the direction of light sources and the direction of sight.
One shading algorithm, the Phong algorithm, utilizes the surface normals of the vertices of each triangle to interpolate the normals at the pixels within the triangle. The normal at each pixel is normalized (i.e., adjusted to have the same magnitude as other normalized normals) and used in the illumination equation to compute each pixel's intensity. In a typical computer graphics system, the Phong algorithm is executed by first approximating the normal at each pixel within a given triangle by bilinear interpolation of the normals of the vertices of that triangle. Each pixel normal (which includes x, y, and z components) is then normalized by dividing the vector by its magnitude (i.e., the square root of the sum of the squares of the x, y, and z components). Put another way, a vector is normalized by multiplying it times 1/.sqroot..eta., where .eta. is the square of the magnitude of the vector. Each normalized pixel normal is then inserted into the illumination equation to determine the intensity for that pixel. This technique requires the performance of relatively complex operations (i.e., division, square root) for each pixel; thus, if implemented in hardware, it would typically require the use of floating point devices. However, the floating point computations are time consuming and thus make it difficult to perform Phong shading in "real-time". Alternately, the Phong algorithm has been implemented in software to eliminate the requirement for floating point hardware, but the execution of the algorithm in software is also relatively time consuming, restricting the performance of real-time Phong shading.